public class BinarySearchTree {
    private static class TreeNode{
        private int val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root;

    public boolean search(int k){
        if(root==null)
            return false;
        TreeNode node = this.root;
        while(node!=null){
            if(node.val==k)
                return true;
            else if(k<node.val)
                node = node.left;
            else
                node = node.right;
        }
        return false;
    }

    public boolean insert(int k){
        if(root==null) {
            root=new TreeNode(k);
            return true;
        }
        TreeNode pr = this.root;
        TreeNode cut = this.root;
        while(cut!=null){
            if(k<cut.val) {
                pr = cut;
                cut = cut.left;
            }
            else if(k>cut.val) {
                pr = cut;
                cut = cut.right;
            }else{
                return false;
            }
        }
        if(k>pr.val){
            pr.right=new TreeNode(k);
        }else{
            pr.left=new TreeNode(k);
        }
        return true;
    }

    public boolean remove(int k){
        if(root==null)
            return false;
        TreeNode pr = null;
        TreeNode cut = this.root;
        while(cut!=null){
            if(k<cut.val) {
                pr = cut;
                cut = cut.left;
            }
            else if(k>cut.val) {
                pr = cut;
                cut = cut.right;
            }else{
                rem(cut,pr);
                return true;
            }
        }
        return false;
    }

    private void rem(TreeNode cut ,TreeNode pr){
        if(cut==null)
            return;
        if(cut.left==null){
            if(cut==root){
                root=cut.right;
            }else{
                if(pr.left== cut){
                    pr.left=cut.right;
                }else{
                    pr.right=cut.right;
                }
            }
        } else if(cut.right==null){
            if(cut==root){
                root=cut.left;
            }else{
                if(pr.left== cut){
                    pr.left=cut.left;
                }else{
                    pr.right=cut.left;
                }
            }
        }else{
            TreeNode rcut = cut.right;
            TreeNode rpr = cut;
            while(rcut.left!=null){
                rpr=rcut;
                rcut=rcut.left;
            }
            cut.val= rcut.val;
            if(rpr.left==rcut)
                rpr.left=rcut.right;
            else
                rpr.right=rcut.right;
        }
    }


}
